package cn.cxq.learning.recursion;

import org.junit.jupiter.api.Test;

/**
 * 链接：https://www.nowcoder.com/questionTerminal/72a5a919508a4251859fb2cfb987a0e6
 * 来源：牛客网
 *
 * [编程题]矩形覆盖
 * 热度指数：562059时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 64M，其他语言128M
 * 算法知识视频讲解
 * 我们可以用2*1的小矩形横着或者竖着去覆盖更大的矩形。请问用n个2*1的小矩形无重叠地覆盖一个2*n的大矩形，总共有多少种方法？
 *
 * 比如n=3时，2*3的矩形块有3种覆盖方法：
 *
 * 示例1
 * 输入
 * 4
 * 输出
 * 5
 */
public class RectCover {

    @Test
    public void test() {
        System.out.println(rectCover(4));
    }

    public int rectCover(int target) {
        if (target == 0 || target == 1) {
            return target;
        }

        return getResult(target);
    }

    // 动态规划解法：
    private int getResult(int target) {
        int[] dp = new int[target + 1];

        dp[0] = 1;
        dp[1] = 1;

        for (int i = 2; i <= target; i++) {
            dp[i] = dp[i - 1] + dp[i - 2];
        }

        return dp[target];
    }
// 其实就是跳台阶啦（斐波那契数列）
//    private int getResult(int target) {
//        if (target == 0) {
//            return 1;
//        }
//
//        if (target == 1) {
//            return 1;
//        }
//
//        return getResult(target - 1) + getResult(target - 2);
//    }
}
